Traffic over current computer and other networks is voluminous, containing many different types and rates of data, and only promises to increase in the future. Future integrated-service networks will support an even wider range of applications with diverse traffic characteristics performance requirements, including by the support of multiple classes of service.
The Available Bit rate (ABR) service defined by the ATM Forum supports data applications and emerging rate-adaptive multimedia applications in Asynchronous Transfer Mode (ATM) networks. Its operation relies on an effective congestion control mechanism. Rate based congestion control has been considered desirable to achieve high performance over high speed networks that are characterized by large bandwidth-delay products. The potential of this scheme to achieve low loss is by maintaining a smooth flow of data with the source rates being adjusted through a feedback mechanism. This allows intermediate systems (switches) to have relatively small buffers while still maintaining high utilizations.
In contrast, although known window flow control has undergone several refinements to also maintain a smooth even flow of data, there are several conditions during which window flow control results in bursty arrivals into the network. The smooth flow of data packets in response to the arrival of acknowledgements is disturbed in cases where there is ack-compression, new flows starting up, or when multiple flows recover from packet loss, and go into slow-start.
Allowing the applications to “fast-start”, that is, to transmit as fast as reasonable upon startup and entry into the network, is desirable for many data applications.
Known rate based congestion control seeks to allocate the source rates so as to achieve high resource utilization, while maintaining feasibility—that is, the capacity of any resource in the network—primarily link bandwidth—is not exceeded at any time. Even a small excess in the source rate, can cause a queue buildup. The ABR service can ensure a particular known notion of fairness—max-min fairness which requires a distributed computation. An incremental computation that scales with the number of connections is described in Kalampoukas, Varma and Ramakrishnan, “An Efficient Rate Allocation Algorithm for ATM Networks Providing Max-Min Fairness”, Proceedings of 6th IFIP International Conference on High Performance Networking, HPN 95, Palma De Mallorca, Spain, Sep. 11-15, 1995, incorporated by reference.
The incremental computation of source rates can potentially result in the rates being infeasible for short intervals (often one round-trip time). Varying feedback delays that result in asynchronous updates to source rates make the control of this period of infeasibility difficult to predict. Several other practical situations also make it difficult to ensure feasibility, which include changes in the capacity due to the presence of higher priority traffic, changes in the number of users as they arrive or depart, and the desire of sources to opportunistically utilize available bandwidth.
The desire to make optimum use of bandwidth extends to the desire of data applications to ramp up as fast as possible on startup and entry into the network. All of these causes transient situations that can result in queue buildups, which are sometimes substantial.
One known way to ensure feasibility is to force a source increasing its rate to delay any increase until all other sources have received and implemented their decreases. Thus, the aggregate rate at a given link will never exceed its capacity. This method introduces considerable delay to sources when they start up or when they are asked to increase their rate, thus impacting applications (and user-perceived performance) adversely. It may also lead to underutilization of resources. In addition, when the bandwidth in the network changes, there is a certain time taken to provide feedback to the sources so that they may change their source-rates accordingly. The build-up of the queues during this transient period cannot be avoided even by schemes that are extremely conservative in ensuring feasibility.
Unlike the scheme for instance proposed in Charny, Ramakrishnan and Lauck, “Time Scale Analysis and Scalability Issues for Explicit Rate Allocation in ATM Networks”, IEEE/ACM Transactions on Networking, August 1996, incorporated by reference, in the ATM Forum's ABR service attempts to maintain feasibility and avoid a large queue buildup by picking conservative values for the “increase parameter”, RIF and the initial cell rate ICR (see Sathaye, “ATM Forum Traffic Management Specification Version 4.0”, (Draft), AF-TM 95-0013R10, ATM Forum Traffic Management Working Group, February 1996, incorporated by reference). However, even a small ICR and RIF, can still result in substantial queue buildups.
Overall then, although attempts have been made to control and manage congestion over computer and other networks and particularly upon startup, none can be viewed to operate optimally or near optimally over a wide range of network conditions.